//1.哈希表


//2.异或
/*
举个例子直观理解
假设 nums = [1,2,1,3,2,5]，目标元素是 3 和 5。

所有元素异或：1^2^1^3^2^5 = 3^5 = 6（二进制 110）。
找最低位的 1：6 的二进制是 110，最低位的 1 在第 1 位（值为 2，即 10）。
分组：
第 1 位为 1 的元素：2（10）、2（10）、3（11）→ A 组。
A 组异或：2^2^3 = 3（抵消后剩下 3）。
第 1 位为 0 的元素：1（01）、1（01）、5（101）→ B 组。
B 组异或：1^1^5 = 5（抵消后剩下 5）。
结果就是 [3,5],正确。
*/
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int n = nums.size();
        if(n==2)
            return {nums[0],nums[1]};
       
        int x = nums[0];
        for(int i = 1; i< n;++i) {
            x^= nums[i];  //x=x1^x2
        }
        int type1=0,type2=0;
        int pos = 0; //找最小位的1位置
      
        for(int i=0;i < 31;++i) {
            int temp = x>>i & 1 ; // 
            if(temp==1) {
                pos= temp<<i;
                break;
            }
        }

        for(int i=0; i<n;++i) {
            if(nums[i]&pos)
                type1^=nums[i];
            else
                type2^=nums[i];
        }


        return {type1, type2};
    }
};
//3.异或(官方)
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorsum = 0;
        for (int num: nums) {
            xorsum ^= num;
        }
        // 防止溢出
        int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;
        for (int num: nums) {
            if (num & lsb) {
                type1 ^= num;
            }
            else {
                type2 ^= num;
            }
        }
        return {type1, type2};
    }
};
/*
int 通常是 32 位有符号整数，表示的范围是： -2147483648（最小，记为 INT_MIN） 到 2147483647（最大，记为 INT_MAX）

正数最大：01111111 11111111 11111111 11111111 → 即 2147483647。（INT_MAX）
负数最小：10000000 00000000 00000000 00000000 → 即 -2147483648（INT_MIN）。
为什么 -INT_MIN 会溢出？
INT_MIN 是 -2147483648，如果我们计算它的相反数 -INT_MIN，结果应该是 2147483648。
但问题来了：
int 类型最大只能存 2147483647（INT_MAX），2147483648 比它大 1，超出了 int 能表示的范围
C++ 中对 INT_MIN 取负号是未定义行为
*/



